# Python library routines
import numpy as np


class Attribute:
    def __init__(self):
        self.Id = 0 
        self.attributeName = ''
        self.isNumeric = False
        self.attributeValues = []
    def cloneAttribute(self):
        attribute = Attribute()
        attribute.Id = self.Id
        attribute.attributeName = self.attributeName
        attribute.isNumeric = self.isNumeric
        attribute.attributeValues = []
        for val in self.attributeValues: attribute.attributeValues.append(val)
        if hasattr(self, "minVal"): attribute.minVal = self.minVal
        if hasattr(self, "maxVal"): attribute.maxVal = self.maxVal
        if hasattr(self, "splits"): attribute.splits = self.splits
        return attribute
    def isNormalized(self):
        if hasattr(self, "minVal") and hasattr(self, "maxVal"):
            return True
        return False        
    def checkAttributeId(self, attr):
        if self.Id != attr.Id: raise Exception("Attributes are not the same: self.Id: " + str(self.Id) + ", attr.Id: " + str(attr.Id))
        if self.attributeName != attr.attributeName: raise Exception("Attributes are not the same: self.attributeName: " + str(self.attributeName) + ", attr.Id: " + str(attr.attributeName))
    
def getColumnIndexForAttributes(attributes):
        columnIndexes = []
        for attr in attributes:
                columnIndexes.append(attr.Id)
        return columnIndexes
def getAttributeById(attributes, Id):
        if Id < len(attributes):
                if (attributes[Id].Id == Id):
                        return attributes[Id]
        for i in range(len(attributes)):
                if (attributes[i].Id == Id):
                        return attributes[i]
        raise Exception("Attribute with Id: " + str(Id) + " does not exist")
class Instance:
    def __init__(self):
        self.Id = 0
        self.nemsId = ""
        self.attributeValues = []
        self.county = ''
        self.lat = ''
        self.longit = ''
        self.nemsId = ''
        self.x = None
        self.y = None
        self.classVal = None
        self.isClassNumeric = None
        self.clusterId = None
        self.nearestNeighborCount = 0 # how many instances point to this instance as nearest neighbor
        self.nearestNeighborCount_Proj = 0 # how many instances point to this instance as neares neighbor in projected data set
        self.originalInst = None
    def createInstance(self):
        instance = Instance()
        instance.Id = self.Id
        instance.county = self.county
        instance.lat = self.lat
        instance.longit = self.longit
        instance.nemsId = self.nemsId
        instance.classVal = self.classVal
        instance.clusterId = self.clusterId
        instance.x = self.x
        instance.y = self.y
        if hasattr(self, 'classRate'): instance.classRate = self.classRate
        return instance
    def cloneInstance(self):
        cloneInstance = self.createInstance()
        cloneInstance.attributeValues = []
        for i in range(len(self.attributeValues)): 
            cloneInstance.attributeValues.append(self.attributeValues[i])
        return cloneInstance
    def getClassVal(self):
        if hasattr(self, 'classRate'):
            return float(self.classRate)
        return float(self.classVal)
    def isProjected(self):
        if len(self.attributeValues) == 0: 
            return True
        return False
    def getDenormalizedValue(self, attribute, index):
                val = float(self.attributeValues[index])
                if attribute.isNormalized():
                        return attribute.minVal + val * (attribute.maxVal - attribute.minVal)
                else:
                        raise Exception("Attribute is not normalized.")
                
def cloneAttributes(origAttributes):
        attributes = []
        for attr in origAttributes:
                attributes.append(attr.cloneAttribute())
        return attributes

class DataSet:
    def __init__(self, isClassNumeric = None):
        self.attributes = []
        self.instances = []
        self.isClassNumeric = isClassNumeric
        self.clusterId = None
        self.statComputed = False
    def createDataSet(self):
        dataSet = DataSet()
        dataSet.isClassNumeric = self.isClassNumeric
        dataSet.attributes = cloneAttributes(self.attributes)
        return dataSet
    def copyDataSet(self):
                dataSet = DataSet()
                dataSet.isClassNumeric = self.isClassNumeric
                dataSet.attributes = self.attributes
                return dataSet
    def randomTestTrainSplit(self, test_ratio):
        test=self.createDataSet()
        train=self.createDataSet()
        insts=[i.cloneInstance() for i in self.instances]
        np.random.shuffle(insts)
        split=int(test_ratio*len(insts))
        test.instances=insts[:split]
        train.instances=insts[split:]
        assert(len(train.instances)+len(test.instances)==len(insts))
        return test, train
    def AbCdSplit(self):
        Ab=self.createDataSet()
        Cd=self.createDataSet()
        Acount=0
        Ccount=0
        for instance in self.instances:
            newinst=instance.cloneInstance()
            newinst.isClassNumeric=False
            prevclass=instance.attributeValues[-1]
            newclass=None
            if ['A','B'].__contains__(prevclass):
                if prevclass=='A': 
                    newclass='1'
                    Acount+=1
                elif prevclass=='B':
                    newclass='0'
                newinst.attributeValues[-1]=newclass
                newinst.classVal=newclass
                Ab.addInstance(newinst)
            
            if ['C','D'].__contains__(prevclass):
                if prevclass=='C': 
                    newclass='1'
                    Ccount+=1
                elif prevclass=='D':
                    newclass='0'
                newinst.attributeValues[-1]=newclass
                newinst.classVal=newclass
                Cd.addInstance(newinst)
            
            if newclass==None:
                raise Exception('Unrecognized Class')
            
        Ab.isClassNumeric=False; Ab.recomputeAttributeValues() 
        Ab.classFreq=float(Acount)/Ab.NrInstances()
        Cd.isClassNumeric=False; Cd.recomputeAttributeValues()
        Cd.classFreq=float(Ccount)/Cd.NrInstances()
        
        return Ab, Cd
            
    def recomputeAttributeValues(self):
        for ind, attribute in enumerate(self.attributes):     
            attribute.attributeValues=[]
            for instance in self.instances:
                value=instance.attributeValues[ind]
                if not attribute.attributeValues.__contains__(value):
                    attribute.attributeValues.append(value)
                
    
    def addInstance(self, instance):
                self.instances.append(instance)
    def NrAttributes(self):
                return len(self.attributes)
    def ClassAttribute(self):
                return self.attributes[self.NrAttributes()-1]
    def NrInstances(self):
                return len(self.instances)
    def setClusterId(self, clusterId):
                for inst in self.instances:
                        inst.clusterId = clusterId
    def getAttributeIndexById(self, attributeId):
                for i in range(self.NrAttributes()):
                        if self.attributes[i].Id == attributeId:
                                return i
                return -1
    def getAttributeById(self, attributeId):
                return self.attributes[self.getAttributeIndexById(attributeId)]
    def findInstanceById(self, instanceId):
                if instanceId < self.NrInstances():
                        if self.instances[instanceId].Id == instanceId:
                                return self.instances[instanceId]
                for instance in self.instances:
                        if instance.Id == instanceId:
                                return instance
                return None
        
    def printDataSetToFile(self, fileName, separator, includeCounty):
        f = open(fileName, 'w')

        for instance in self.instances:
            line = ''
            
            for i in range(self.NrAttributes()):
                if i != 0: line = line + separator
                line = line + str(instance.attributeValues[i])
            if includeCounty: line = line + separator + str(instance.county)
            f.write(line + '\n')
        f.close()

    def printProjectedDataSetToFile(self, fileName, separator, includeCounty):
        f = open(fileName, 'w')
        for instance in self.instances:
            line = ""
            line = str(instance.x) + separator + str(instance.y) + separator + str(instance.classVal)
            if includeCounty: line = line + separator + str(instance.county)
            f.write(line + '\n')
            f.close()

    def squareDistance(self, instance1, instance2, maxSquareDist = None):
        if instance1.isProjected() == True:
            return self.squareDistanceOnProjected(instance1, instance2, maxSquareDist)
        return self.squareDistanceOnAllAttributes(instance1, instance2, maxSquareDist)

    def dist(self, instance1, instance2, maxSquareDist = None):
        return float(self.squareDistance(instance1, instance2, maxSquareDist)**0.5)

    def squareDistanceOnAllAttributes(self, instance1, instance2, maxSquareDist = None):
                sumSqr = 0

                for i in range(self.NrAttributes() - 1):
                        v1 = instance1.attributeValues[i]
                        v2 = instance2.attributeValues[i]

                        if v1 == "?" and v2 == "?": continue

                        if self.attributes[i].isNumeric:
                                if v1 == "?": v1 = furthest_numeric(float(v2), 0, 1)
                                else: v1 = float(v1)
                                if v2 == "?": v2 = furthest_numeric(v1, 0, 1)
                                else: v2 = float(v2)
                                sumSqr += (v1-v2)**2
                        else:
                                if (v1 != v2): sumSqr += 1

                        if maxSquareDist != None:
                                if sumSqr > maxSquareDist:
                                        return sumSqr

                return sumSqr

    def squareDistanceOnProjected(self, instance1, instance2, maxSquareDist = None):
                sumSqr = 0

                sumSqr += (instance1.x - instance2.x)**2

                if maxSquareDist != None:
                        if sumSqr > maxSquareDist:
                                return sumSqr

                sumSqr += (instance1.y - instance2.y)**2

                return sumSqr



    def findMostDistant(self, instance):
        maxDist = 0
        indDist = 0

        for i in range(self.NrInstances()):
            dist = self.squareDistance(instance, self.instances[i])

            if dist > maxDist:
                maxDist = dist
                indDist = i
        
        return self.instances[indDist]

    def findNearestNeighbors(self, instance, k, version):
        nearestNeighbors = {}        
        nearestNeighborsSqrDist = []    #the list of corresponding Sqr Distance

        for i in range(self.NrInstances()):
            if self.instances[i].Id == instance.Id: continue
            if len(nearestNeighborsSqrDist) < k:
                #fill the first k instances
                sqrDist = self.squareDistance(instance, self.instances[i])

                #get the insert position for sqr distance
                ind = getInsertIndex_2(nearestNeighborsSqrDist, sqrDist)
                insertItem(nearestNeighborsSqrDist, ind, sqrDist)

                if not (sqrDist in nearestNeighbors): nearestNeighbors[sqrDist] = []
                nearestNeighbors[sqrDist].append(self.instances[i])
                    
            else:
                # calculate the distance btw instance and the i-th instance
                # the calculation of sqrDistance stops if it exceeds the maximum distance of the current
                # neighbors
                sqrDist = self.squareDistance(instance, self.instances[i], nearestNeighborsSqrDist[k-1])
                
                ind = getInsertIndex_2(nearestNeighborsSqrDist, sqrDist)
                if ind < k: 
                    #this happens when sqrDist is less than at least one of 
                    #the square distances of the current nearest neighbors
                    insertItem(nearestNeighborsSqrDist, ind, sqrDist)    
                    nearestNeighborsSqrDist.pop()

                if not (sqrDist in nearestNeighbors): nearestNeighbors[sqrDist] = []
                nearestNeighbors[sqrDist].append(self.instances[i])

        if version == "v1":
            neighbors = []
            prevSqrDist = None
            for sqrDist in nearestNeighborsSqrDist:
                #print "Dist: " + str(sqrDist) + ", " + str(len(nearestNeighbors[sqrDist]))
            
                if sqrDist != prevSqrDist:
                    neighbors += nearestNeighbors[sqrDist]
            
                prevSqrDist = sqrDist

            #print "Neighbors: " + str(len(neighbors))
            return neighbors

        elif version == "v2":
            neighbors = []
            for sqrDist in nearestNeighborsSqrDist:
                #print "Dist: " + str(sqrDist) + ", " + str(len(nearestNeighbors[sqrDist]))

                if len(nearestNeighbors[sqrDist]) == 1: neighbors.append(nearestNeighbors[sqrDist][0])
                else: neighbors.append(randomPop(nearestNeighbors[sqrDist]))

            #print "Neighbors: " + str(len(neighbors))
            return neighbors
   
   

        

   

    def estimateScoreFromNearestNeighbors(self, instance, k, method):
        neighbors = self.findNearestNeighbors(instance, k, "v2")
        ret = None
        if method == "Median":
            scores = []
            for neigh in neighbors: 
                scores.append(neigh.classVal)
            scores.sort()
            ret = scores[len(scores)/2]
        else:
            ret = 0
            for neigh in neighbors: ret += neigh.classVal
            ret = float(ret)/float(len(neighbors))
        return ret


    def estimateClassFromNearestNeighbors_Exponential(self, instance, k, theta = None):
        score = self.calculateExponentialExtrapolationFromNeighbors(instance, k)
        if self.isClassNumeric == True:
            return score
        else:
            return self.estimateDiscreteScoreFromRawScore(score, theta)

    def calculateExponentialExtrapolationFromNeighbors(self, instance, k):
        neighbors = self.findNearestNeighbors(instance, k, "v2")
        score = 0
        sumWeights = 0
        for neigh in neighbors:
            dist = self.dist(instance, neigh)
            weight = float(10000000000000)
            if dist != 0: weight = float(1)/dist
            sumWeights += weight

        for neigh in neighbors:
            dist = self.dist(instance, neigh)
            weight = float(10000000000000)
            if dist != 0: weight = float(1)/dist
            score += (weight/sumWeights) * float(neigh.classVal!='0')
        #print [i.classVal for i in neighbors]+[score]
        return score

    def estimateDiscreteScoreFromRawScore(self, score, theta):
        if theta == None: theta = 0.5
        if score < theta:
            return "0"
        return "1"

    def applyNearestNeighbor(self, k, filterDs):
        print "Neighbors"
        minNeigh = 100000000
        maxNeigh = -1
        neighborsNr = {}
        # find all nearest neighbors for each instance
        for instance in self.instances:
            neighbors = []
            neighbors = self.findNearestNeighbors(instance, k, "v1")

            if len(neighbors) in neighborsNr: neighborsNr[len(neighbors)] += 1
            else: neighborsNr[len(neighbors)] = 1

            if len(neighbors) < minNeigh: minNeigh = len(neighbors)
            if len(neighbors) > maxNeigh: maxNeigh = len(neighbors)
            
            if neigh.isProjected == False:
                for neigh in neighbors: neigh.nearestNeighborCount += 1
            else:
                for neigh in neighbors: neigh.nearestNeighborCount_Proj += 1

        # browse all neighbors
        nr = 0
        if neigh.isProjected == False:
            for instance in self.instances:
                if instance.nearestNeighborCount > 0: filterDs.addInstance(instance)
        else:
            for instance in self.instances:
                                if instance.nearestNeighborCount_Proj > 0: filterDs.addInstance(instance)
    
    def project(self, selectedIndex = None, east = None, west = None, nrInstances = None, logFilter = False):
        if east == None and west == None and nrInstances == None:
            instance = one(self.instances) #pick a random instance i
            #selectedIndex = 70            
            if selectedIndex != None: instance = self.instances[selectedIndex]
            #print str(instance.Id)            
            east = self.findMostDistant(instance) #find most distant instance east from i
            west = self.findMostDistant(east) #find most distant isntace west from east
            nrInstances = self.NrInstances()
            self.east = east
            self.west = west

        c = ((self.squareDistance(west,east))**0.5)/(nrInstances**0.5)

        #print "East:" + str(east.Id)
        #print "West:" + str(west.Id)
        #print "c:" + str(c)

        projectedDataSet = self.copyDataSet()

        for i in range(self.NrInstances()):
            instance = self.instances[i]
            
            a = ((self.squareDistance(west,instance))**0.5)/(nrInstances**0.5)
            b = ((self.squareDistance(east,instance))**0.5)/(nrInstances**0.5)

            x = (a**2 + c**2 - b**2)/(2*c)
            y = 0
            if (a**2 - x**2) > 0:
                y = (a**2 - x**2)**0.5

            if logFilter == True:
                if x == 0 or y == 0: continue
                x = math.log(x)
                y = math.log(y)

            projectedInstance = instance.cloneInstance()
            projectedInstance.x = x
            projectedInstance.y = y
            projectedDataSet.addInstance(projectedInstance)

        projectedDataSet.east = east
        projectedDataSet.west = west

        return projectedDataSet

    def split(self, n):
        instances = self.instances[:]
        instances_0 = []
        instances_1 = []
        for inst in instances:
            if inst.classVal == "0": 
                instances_0.append(inst)
            else: 
                instances_1.append(inst)
        
        shuffle(instances_0)
        shuffle(instances_1)

        size0 = int(len(instances_0)/n)
        size1 = int(len(instances_1)/n)

        k0 = 0
        k1 = 0

        dataSets = []
        
        for i in range(n):
            dataSet = self.copyDataSet()
            dataSet.attributes = self.attributes

            for j in range(size0):
                if k0 < len(instances_0):
                    dataSet.addInstance(instances_0[k0])
                    k0 += 1

            for j in range(size1):
                if k1 < len(instances_1):
                    dataSet.addInstance(instances_1[k1])
                    k1 += 1

            dataSets.append(dataSet)

        
        while (k0 < len(instances_0)):
            dataSets[k0%n].addInstance(instances_0[k0])
            k0 += 1

        while (k1 < len(instances_1)):
            dataSets[k1%n].addInstance(instances_1[k1])
            k1 += 1

        return dataSets

    def splitDataSetByClusterId(self, clusters):
        dataSets = {}
        for cl in clusters:
            dataSet = self.createDataSet()
            dataSets[cl.clusterId] = dataSet
            

        dataSet = self.createDataSet()
        dataSet.attributes = self.attributes
        dataSets[-1] = dataSet

        for instance in self.instances:
            if instance.clusterId in dataSets:
                dataSets[instance.clusterId].addInstance(instance)
            else:
                dataSets[-1].addInstance(instance)

        return dataSets

        def sample(self, x, trainDs, testDs):
                instances = self.instances[:]
                shuffle(instances)

                size = len(instances) - int((float(x)/float(100))*len(instances))

        for i in range(size):
            trainDs.addInstance(instances[i])

        for i in range(len(instances) -size):
            testDs.addInstance(instances[i])

    def sample(self, x, ds2):
        dataSet = ds2.createDataSet()
        dataSet.attributes = ds2.attributes
        
        instances = self.instances[:]
        shuffle(instances)

        size1 = int((float(x))*len(instances))
        size2 = int(2*(float(x))*len(instances))
        if size1 < 2: size1 = min(len(instances), 2)
        size2 = min(size2, len(instances)-size1)    
        
        list1 = []
        for i in range(size1): 
            list1.append(instances[i].originalInst)
            print instances[i].nemsId

        list2 = []
        sumDist = 0
        for i in range(size1, size2):
            dist = findMinAirDistance(instances[i].originalInst, list1)
            list2.append((instances[i].originalInst, dist))
            sumDist += dist
        list2.sort(key = lambda inst: inst[1]) #sort instances by distance

        print ""

        for i in range(min(size1, len(list2))):
            list1.append(list2[i][0])
            print list2[i][0].nemsId

        print

        dataSet.instances = list1

        nr = 0
        if size1 < size2: nr = size2 - size1

        dataSet.sumDist = sumDist
        dataSet.nr1 = nr

        print

        instances2 = self.instances[:]
        shuffle(instances2)
        i = 0
        k = 0
        while (i < len(instances2) and k < size1):
            nemsId = instances2[i].nemsId
            inst = findInstanceByNemsId(dataSet.instances, nemsId)
            if inst == None: 
                print nemsId
                k += 1
            i += 1        

        return dataSet
        
    def computeClassStatistics(self):
        if self.statComputed == False:
            if self.isClassNumeric == True:
                self.computeStatisticsForNumericClass()
            elif self.isClassNumeric == False:
                self.computeStatisticsForDiscreteClass()
            self.statComputed = True

    def computeStatisticsForNumericClass(self):
        size = self.NrInstances()
        self.instances.sort(key = lambda instance: instance.classVal)

        self.minScore = 0
        self.q1Score = 0
        self.medianScore = 0
        self.q3Score = 0
        self.maxScore = 0
        self.meanScore = 0
        self.sumScore = 0
        self.sumSquareScore = 0
        self.varianceScore = 0

        if size > 0:
            self.minScore = self.instances[0].classVal
            self.q1Score = self.instances[size/4].classVal
            self.medianScore = self.instances[size/2].classVal
            self.q3Score = self.instances[(3*size)/4].classVal
            self.maxScore = self.instances[size - 1].classVal

        for instance in self.instances:
            self.sumScore += instance.classVal
            self.sumSquareScore += instance.classVal**2

        if size > 0:
            self.meanScore = float(self.sumScore)/float(size)
        if size > 1:
                        self.varianceScore = (self.sumSquareScore - ((self.sumScore ** 2) / float(size) )) / (float(size)-1)

    def computeStatisticsForDiscreteClass(self):
        size = len(self.instances)

        self.classFreq = {}
        self.entropy = 0

        if len(self.attributes) != 0:
            for classVal in self.attributes[len(self.attributes)-1].attributeValues:        
                self.classFreq[classVal] = 0

        for instance in self.instances:
            if instance.classVal not in self.classFreq: self.classFreq[instance.classVal] = 0
            self.classFreq[instance.classVal] += 1

        self.entropy = estimateEntropy(self.classFreq)
        self.classMode = computeClassMode(self.classFreq)
        self.classRate = 0
        if (self.NrInstances() != 0):
            for val in self.classFreq: self.classRate += float(self.classFreq[val]) * ( float(self.classFreq[val]) / float(self.NrInstances()) ) 
         
                
    def getClassFreq(self, classVal):
        if self.isClassNumeric == True:
            raise Exception("Class must be discrete")
        self.computeClassStatistics()
        return self.classFreq[classVal]
                
    def FayyadIraniDiscretizer(self, label):
        discDataSet = self.createDataSet()
        for i in range(len(self.attributes)):
            discAttribute = discDataSet.attributes[i]
            discAttribute.splits = None
            self.attributes[i].checkAttributeId(discAttribute)
            if self.attributes[i].isNumeric and i != len(self.attributes)-1:
                pairs = self.GetPairs(i, label, True)
                pairs.sort(key = lambda pair: 0-pair.x)
                discAttribute.splits = self.getColumSplitsForFayyadIrani(pairs)
                discAttribute.isNumeric = False
                discAttribute.attributeValues = getAttributeValuesFromSplits(discAttribute.splits)

        for instance in self.instances:
            discInstance = discDataSet.discretizeInstance(instance)
            discDataSet.addInstance(discInstance)

        return discDataSet


    def EqualWidthDiscretization(self, label, nrBins=10):
        dataSet = self.createDataSet()
        for i in range(len(self.attributes)):
            discAttribute = dataSet.attributes[i]
            discAttribute.splits = None
            self.attributes[i].checkAttributeId(discAttribute)
            if self.attributes[i].isNumeric and i != len(self.attributes)-1:
                pairs = self.GetPairs(i, label, True)
                pairs.sort(key = lambda pair: pair.x)
                discAttribute.splits = self.getColumnSplitsForEqualWidth(pairs, nrBins)
                discAttribute.isNumeric = False
                discAttribute.attributeValues = getAttributeValuesFromSplits2(discAttribute.splits)
        #print('ranges calulated')
        for instance in self.instances:
                        discInstance = dataSet.discretizeInstance(instance)
                        dataSet.addInstance(discInstance)

        return dataSet
    
    def discretizeDataSet(self, attributes):
        discDataSet = self.createDataSet()
        discDataSet.attributes = cloneAttributes(attributes)
        self.computeClassStatistics()
        discDataSet.classFreq=self.classFreq
        for instance in self.instances:
            discInstance = discDataSet.discretizeInstance(instance)
            discDataSet.addInstance(discInstance)
        return discDataSet

    def discretizeNumericClassByMedian(self):
        self.computeClassStatistics()
        dataSet = self.createDataSet()
        dataSet.isClassNumeric = False
        dataSet.attributes[len(self.attributes)-1].isNumeric = False
        dataSet.attributes[len(self.attributes)-1].attributeValues = ["0", "1"]            

        for instance in self.instances:
            newInstance = instance.createInstance()
            for val in instance.attributeValues: newInstance.attributeValues.append(val)
            if instance.classVal < self.medianScore:
                                newInstance.attributeValues[len(newInstance.attributeValues)-1] = "0"
                                newInstance.classVal = "0"
            else:
                                newInstance.attributeValues[len(newInstance.attributeValues)-1] = "1"
                                newInstance.classVal = "1"            
            dataSet.addInstance(newInstance)

        return dataSet

    def getColumSplitsForFayyadIrani(self, pairs):
        splits = []
        self.splitColumnForFayyadIrani(pairs, splits)
        splits = unique(splits)
        splits.sort()
        return splits

    def getColumnSplitsForEqualWidth(self, pairs, nrBins):
        splits = []
        binSize = (pairs[len(pairs)-1].x - pairs[0].x)/nrBins
        current = pairs[0].x    
        for i in range(10):
            splits.append(current)
            current += binSize
        return splits

    def splitColumnForFayyadIrani(self, pairs, splits):
        n = len(pairs)
        if n < 2: return

        classFreq = getLabelFrequenciesFromPairs(pairs)
        currentEntropy = estimateEntropy(classFreq)
        k = len(classFreq)

        #print ""
        #print "Entropy before split: " + str(currentEntropy)

        classFreq1 = {}
        classFreq2 = {}
        for c in classFreq: 
            classFreq1[c] = 0
            classFreq2[c] = classFreq[c]

        bestValue = None
        splitIndex = None
        entropy1_best = None
        entropy2_best = None
        k1_best = None
        k2_best = None

        for i in range(n):
            classFreq1[pairs[i].c] += 1
            classFreq2[pairs[i].c] -= 1

            entropy1 = estimateEntropy(classFreq1)
            entropy2 = estimateEntropy(classFreq2)

            value = (float(i)/float(n))*entropy1 + (1 - float(i)/float(n))*entropy2

            if bestValue == None:
                bestValue = value
                splitIndex = i
                entropy1_best = entropy1
                entropy2_best = entropy2
                k1_best = len(classFreq1)
                k2_best = len(classFreq2)

            elif value < bestValue:
                bestValue = value
                splitIndex = i
                entropy1_best = entropy1
                entropy2_best = entropy2
                k1_best = len(classFreq1)
                k2_best = len(classFreq2)

        #print str(pairs[0].x) + " " + str(pairs[splitIndex].x) + " " + str(pairs[len(pairs)-1].x)
        splits.append(pairs[splitIndex].x)

        #print "Entropy of the split: " + str(bestValue)

        if  bestValue < currentEntropy:
            stop = self.evaluateSplitStoppingCriteria(n, currentEntropy, k, 
                                     entropy1_best, k1_best, 
                                     entropy2_best, k2_best, splitIndex)
            if stop == False and splitIndex != 0:
                self.splitColumnForFayyadIrani(pairs[0:splitIndex+1], splits)
            if stop == False and splitIndex != n-1:
                self.splitColumnForFayyadIrani(pairs[splitIndex+1:n], splits)

    def evaluateSplitStoppingCriteria(self, n, entropy, k, entropy1, k1, entropy2, k2, splitIndex):
        #n - number of instances
        #entropy - entropy before split
        #k - number of labels in the instance set
        #entropy1, entropy2 - entropy of the respective first and second split
        #k1, k2 - numbe of labels in the respective first and second split
        #splitIndex - the split index

        #This function uses the Minimal Description Length Principle to determine
        #the stopping criteria of the Fayad-Irani discretization algorithm
        delta = math.log(3**k - 2,2) - (k*entropy - k1*entropy1 - k2*entropy2)
        entropy_split = (float(splitIndex)/float(n))*entropy1 + (1 - float(splitIndex)/float(n))*entropy2
        gain = entropy - entropy_split
        stopCriteria = math.log(n-1, 2)/float(n) + float(delta)/float(n)
        #print "Gain: " + str(gain) + ", Stop: " + str(stopCriteria)
        if gain < stopCriteria:
            return True
        else:
            return False

    def discretizeInstance(self, instance):
        discInstance = instance.createInstance()
        discInstance.attributeValues = []
        for i in range(len(instance.attributeValues)):
            discVal = ""
            val = instance.attributeValues[i]
            attribute = self.attributes[i]
            if val == "?":
                discVal = "?"            
            elif attribute.splits != None:
                discVal = discretizeValue(float(val), attribute.splits)
            else:
                discVal = val
            discInstance.attributeValues.append(discVal)
        return discInstance

    def discretizeInstance2(self, instance):
        discInstance = instance.createInstance()
        discInstance.attributeValues = []
        for i in range(len(instance.attributeValues)):
            discVal = ""
            val = instance.attributeValues[i]
            attribute = self.attributes[i]
            if attribute.splits != None:
                discVal = discretizeValue2(float(val), attribute.splits)
            else:
                discVal = val
            discInstance.attributeValues.append(discVal)
        return discInstance


    def estimateColumnsEntropy(self, label):
        #returns a list of pairs consisting of attribute indexes and corresponding entropies
        #the list is sorted in increasing order by entropy 
        columnEntropy = []
        for i in range(len(self.attributes)-1):
            if self.attributes[i].isNumeric == True:
                raise Exception("estimateColumnsEntropy - Attribute: " + 
                        self.attributes[i].attributeName + " is numeric")
            columnEntropy.append((i, self.estimateEntropyOfSplit(i, label)))
        columnEntropy.sort(key = lambda x: x[1]) #sort by entropy
        return columnEntropy        

    def featureReductionViaInfoGain(self, label, percentage, columnEntropy=None):
        #column entropy is a list of pairs (attribueIndex, entropy) ordered in increasing order by entropy
        if columnEntropy == None:
            columnEntropy = self.estimateColumnsEntropy(label)

        length = float(percentage)*float(len(columnEntropy))
        if not length.is_integer(): length = int(length) + 1 
        else: length = int(length)

        selectedAttributes = []
        for i in range(length):
            selectedAttributes.append(columnEntropy[i][0])
        selectedAttributes.append(len(self.attributes)-1)    
        selectedAttributes.sort()
        
    
        return selectedAttributes

    def featureReductionViaInfoGain2(self, label):
        columnEntropy = {}
        maxEntropy = None
        for i in range(len(self.attributes)-1):
            if self.attributes[i].isNumeric == True:
                raise Exception("featureReductionViaInfoGain - Attribute: " +
                    self.attributes[i].attributeName + " is numeric")
            columnEntropy[i] = self.estimateEntropyOfSplit(i, label)
            if maxEntropy == None: maxEntropy = columnEntropy[i]
            elif columnEntropy[i] > maxEntropy: maxEntropy = columnEntropy[i]

        selectedAttributes = []
        for column in columnEntropy:
            if columnEntropy[column] < 0.75*maxEntropy:
                selectedAttributes.append(column)
        selectedAttributes.append(len(self.attributes)-1)
        selectedAttributes.sort()


        return selectedAttributes

        #l = sorted([(value,key) for (key,value) in columnEntropy.items()])



    def estimateEntropyOfSplit(self, columnIndex, label):
        attribute_value_class_freq = {}
        attribute_value_freq = {}

        for instance in self.instances:
            attrValue = instance.attributeValues[columnIndex]
            labelValue = ""
            if label.lower() == "class" and not self.isClassNumeric:
                labelValue = instance.classVal
            elif label.lower() == "class" and self.isClassNumeric:
                                raise Exception("Class should not be numeric!")
            elif label.lower() == "cluster":
                labelValue = instance.clusterId
            else:
                raise Exception("Unknown label type: " + label)
            if attrValue not in attribute_value_freq:
                attribute_value_freq[attrValue] = 0
            if attrValue not in attribute_value_class_freq:
                attribute_value_class_freq[attrValue] = {}
            if labelValue not in attribute_value_class_freq[attrValue]:
                attribute_value_class_freq[attrValue][labelValue] = 0
            attribute_value_freq[attrValue] += 1
            attribute_value_class_freq[attrValue][labelValue] += 1
            

        entropy = 0
        n = len(self.instances)
        for attrValue in attribute_value_class_freq:
            p = float(attribute_value_freq[attrValue])/float(n)
            entropy += p*estimateEntropy(attribute_value_class_freq[attrValue])

        return entropy

    def computeNumericAttrStats(self, i):
        attributeValues = []
        for instance in self.instances:
                if instance.attributeValues[i] != "?":
                        attributeValues.append(float(instance.attributeValues[i]))
        attributeValues.sort()
        l = len(attributeValues)
        q0 = attributeValues[0]
        q1 = attributeValues[l/4]
        q2 = attributeValues[l/2]
        q3 = attributeValues[(3*l)/4]
        q4 = attributeValues[l-1]
        

        return [q0, q1, q2, q3, q4]


    def initializeAttrValFrequencies(self):
        self.attributeValuesFreq = {}
        for i in range(self.NrAttributes()-1):
            attribute = self.attributes[i]
            if attribute.isNumeric == False:
                self.attributeValuesFreq[attribute.Id] = {}
                for val in attribute.attributeValues:
                    self.attributeValuesFreq[attribute.Id][val] = {}
                    self.attributeValuesFreq[attribute.Id]["?"] = {}
                    if self.isClassNumeric == False:
                        for label in self.ClassAttribute().attributeValues:
                            self.attributeValuesFreq[attribute.Id][val][label] = 0
                            self.attributeValuesFreq[attribute.Id]["?"][label] = 0
                    self.attributeValuesFreq[attribute.Id][val]["TOTAL"] = 0
                    self.attributeValuesFreq[attribute.Id]["?"]["TOTAL"] = 0

    def initializeAttributeModes(self):
        self.attributeModes = {}
        for i in range(self.NrAttributes()-1):
            attribute = self.attributes[i]
            if attribute.isNumeric == False:
                                self.attributeModes[attribute.Id] = None

    def initializeAttributeMeans(self):
        self.attributeMeans = {}
        self.nrInstances = {}
        for i in range(self.NrAttributes()-1):
            attribute = self.attributes[i]
            if attribute.isNumeric == True:
                    self.attributeMeans[attribute.Id] = 0
                    self.nrInstances[attribute.Id] = 0
        self.meanX = 0
        self.meanY = 0

    def computeAttributeValuesFrequencies(self):
        self.initializeAttrValFrequencies()
        for instance in self.instances:
            for i in range(self.NrAttributes()-1):
                if self.attributes[i].isNumeric == False:
                    attributeId = self.attributes[i].Id
                    attributeValue = instance.attributeValues[i]
                    if self.isClassNumeric == False:
                        #print [attributeId,attributeValue,instance.classVal]
                        self.attributeValuesFreq[attributeId][attributeValue][instance.classVal] += 1
                    self.attributeValuesFreq[attributeId][attributeValue]["TOTAL"] += 1

    def computeAttributeModes(self):
        self.computeAttributeValuesFrequencies()
        self.initializeAttributeModes()
        for attributeId in self.attributeValuesFreq:
            maxFreq = 0
            maxFreqVal = None
            for val in self.attributeValuesFreq[attributeId]:   
                if self.attributeValuesFreq[attributeId][val]["TOTAL"] > maxFreq:
                    maxFreq = self.attributeValuesFreq[attributeId][val]["TOTAL"]
                    maxFreqVal = val
            self.attributeModes[attributeId] = maxFreqVal
                    
    def computeAttributeMeans(self):
        self.initializeAttributeMeans()
        for instance in self.instances:
            for i in range(self.NrAttributes()-1):
                if self.attributes[i].isNumeric == True:
                    attributeId = self.attributes[i].Id
                    attributeValue = instance.attributeValues[i]
                    if (attributeValue != "?"):
                        self.attributeMeans[attributeId] += float(attributeValue)
                        self.nrInstances[attributeId] += 1
            self.meanX += instance.x
            self.meanY += instance.y


                
        for attributeId in self.attributeMeans:
                if self.nrInstances[attributeId] != 0:
                        self.attributeMeans[attributeId] = float(self.attributeMeans[attributeId])/float(self.nrInstances[attributeId])
                else:
                        self.attributeMeans[attributeId] = "?"

        if (self.NrInstances() != 0):
                self.meanX = float(self.meanX)/float(self.NrInstances())
                self.meanY = float(self.meanY)/float(self.NrInstances())


    def computeCentroid(self):
        self.computeClassStatistics()
        self.computeAttributeModes()
        self.computeAttributeMeans()

        instance = Instance()

        for i in range(self.NrAttributes()-1):
                attribute = self.attributes[i]
                if attribute.isNumeric == True:
                        instance.attributeValues.append(self.attributeMeans[attribute.Id])
                else:
                        instance.attributeValues.append(self.attributeModes[attribute.Id])

        instance.x = self.meanX
        instance.y = self.meanY
        if (self.isClassNumeric == True):
                instance.classVal = self.meanScore
        else:
                instance.classVal = self.classMode
                instance.classRate = self.classRate
        instance.attributeValues.append(instance.classVal)

        return instance

    def Likelihood(self, instance):
        m = 2
        k = 1

        like = -1000000000000000
        predClass = None

        strV = ""

        for classValue in self.attributes[len(self.attributes)-1].attributeValues:
            prior = float(self.classFreq[classValue] + k)/float(self.NrInstances() + k * len(self.classFreq))
            temp = math.log(prior)
            for i in range(len(self.attributes)-1):
                attributeValue = instance.attributeValues[i]
                if self.attributeValuesFreq[i].has_key(attributeValue):
                    temp += math.log(float(self.attributeValuesFreq[i][attributeValue][classValue] + m * prior)/float(self.classFreq[classValue] + m))

            strV += str(classValue) + ": " + str(temp) + " " 

            if temp >= like:
                                like = temp
                                predClass = classValue
                        #print str(c) + " " + str(temp)

        #print "instanceId: " + str(instance.Id) + " " + strV
        return predClass
        
    def GetPairs(self, columnIndex, label, isAttributeNumeric):
        pairs = []
        for instance in self.instances:
            if instance.attributeValues[columnIndex] == "?": continue
            if isAttributeNumeric == True:
                attributeVal = float(instance.attributeValues[columnIndex])
            else:
                attributeVal = instance.attributeValues[columnIndex]
            if label.lower() == "class" and not self.isClassNumeric:
                pairs.append(Pair(attributeVal, instance.classVal))
            elif label.lower() == "class" and self.isClassNumeric:
                pairs.append(Pair(attributeVal, instance.classVal))
            elif label.lower() == "cluster":
                pairs.append(Pair(attributeVal, instance.clusterId))
            else:
                raise Exception("Unknown label type: " + label)
        return pairs

    def NormalizeDataSet(self, outlierRemoval):
        dataSet = self.createDataSet()
        l = len(self.instances)
        
        for i in range(len(self.attributes)):
            if self.attributes[i].isNumeric and i != len(self.attributes)-1:
                [minV, q1, median, q3, maxV] = self.computeNumericAttrStats(i)
                iqr = q3 - q1
                if outlierRemoval == True:
                        dataSet.attributes[i].minVal = max(minV, q1 - 1.5*iqr)
                        dataSet.attributes[i].maxVal = min(maxV, q3 + 1.5*iqr)
                else:
                        dataSet.attributes[i].minVal = minV
                        dataSet.attributes[i].maxVal = maxV

        for instance in self.instances:
            normInstance = instance.createInstance()
            if outlierRemoval: dataSet.normalizeInstanceWithOutlierRemoval(instance, normInstance)
            else: dataSet.normalizeInstanceWithoutOutlierRemoval(instance, normInstance)
            dataSet.addInstance(normInstance)
        return dataSet

    def normalizeInstanceWithOutlierRemoval(self, instance, normInstance):
        normInstance.attributeValues = []
        for i in range(len(instance.attributeValues)):
            val = instance.attributeValues[i]
            attribute = self.attributes[i]
            if attribute.isNumeric == True and i != len(self.attributes)-1 and val != "?":
                val = float(val)
                if val < attribute.minVal:
                    val = 0
                elif val > attribute.maxVal:
                    val = 1
                elif attribute.maxVal == attribute.minVal:
                                        val = attribute.maxVal
                else:
                    val = (val - attribute.minVal)/(attribute.maxVal - attribute.minVal)
            normInstance.attributeValues.append(val)

    def normalizeInstanceWithoutOutlierRemoval(self, instance, normInstance):
        normInstance.attributeValues = []
        for i in range(len(instance.attributeValues)):
            val = instance.attributeValues[i]
            attribute = self.attributes[i]
            if attribute.isNumeric == True and i != len(self.attributes)-1 and val != "?":
                val = float(val)
                if attribute.maxVal == attribute.minVal:
                                        val = attribute.maxVal
                else:
                    val = (val - attribute.minVal)/(attribute.maxVal - attribute.minVal)
            normInstance.attributeValues.append(val)

            
    def ApplyNormalization(self, attributes, outlierRemoval):
        dataSet = self.createDataSet()
        for i in range(len(dataSet.attributes)):
            dataSet.attributes[i].checkAttributeId(attributes[i])
            if dataSet.attributes[i].isNumeric and i != len(dataSet.attributes)-1:
                dataSet.attributes[i].minVal = attributes[i].minVal
                dataSet.attributes[i].maxVal = attributes[i].maxVal

        for instance in self.instances:
            normInstance = instance.createInstance()
            if outlierRemoval: dataSet.normalizeInstanceWithOutlierRemoval(instance, normInstance)
            else: dataSet.normalizeInstanceWithoutOutlierRemoval(instance, normInstance)
            dataSet.addInstance(normInstance)

        return dataSet                        

        def denormalizeInstance(self, instance):
                newInstance = instance.createInstance()
                for i in range(self.NrAttributes()-1):
                        val = instance.getDenormalizedValue(self.attributes[i], i)
                        newInstance.attributeValues.append(val)
                newInstance.attributeValues.append(instance.classVal)
                return newInstance


    def exportDataSetToCsv(self, fileName):
        self.instances.sort(key = lambda inst: inst.Id)

        f = open(fileName, "w")

        #write header
        line = ""
        for attr in self.attributes: 
            if line != "": line += ","
            line += str(attr.attributeName)
        line += "\n"
        f.write(line)


        #write each instance
        for inst in self.instances:
            line = ""
            for val in inst.attributeValues: 
                if line != "": line += ","
                line += str(val)
            line += "\n"

            f.write(line)
        
        f.close()

    def exportDataSetToArff(self, fileName):
        f = open(fileName, "w")
        f.write("@relation " + fileName + "\n\n")
    
        #write attributes
        for attr in self.attributes:
            line = "@attribute " + attr.attributeName + " "
            if attr.isNumeric == True: line += "numeric"
            else:
                vals = ""            
                for val in attr.attributeValues:
                    if vals != "": vals += ","
                    vals += val
                if vals!="string":
                    line += "{" + vals + "}"
                else:
                    line += "string"
            line += "\n"
            f.write(line)
    
        f.write("\n@data\n")

        for inst in self.instances:
            line = ""
            for val in inst.attributeValues:
                if line != "": line += ","
                line += str(val)
            line += "\n"
            f.write(line)

        f.close()

    def applyFSS(self, columnIndexes):
        dataSet = self.createDataSet()
        selectAttributes = []
        for ind in columnIndexes: selectAttributes.append(getAttributeById(dataSet.attributes, ind))
        dataSet.attributes = selectAttributes

        for instance in self.instances:
            fssInstance = instance.createInstance()
            fssInstance.attributeValues = []
            for i in columnIndexes:
                fssInstance.attributeValues.append(instance.attributeValues[i])
            dataSet.addInstance(fssInstance)

        return dataSet

    def condenseFromSamples(self, samples):
        dataSet = self.createDataSet()        
        dataSet.attributes = self.attributes

        for clusterId in samples:
            dataSet.instances += samples[clusterId].instances

        return dataSet

        def exportToCSV(self, f):
                #write attributes
                line = "InstanceId, ClusterId, x, y"
                for attr in self.attributes:
                        line += ", " + attr.attributeName
                if attr.isNumeric == True: line += "_$"
                if self.isClassNumeric == False: line += ", rate"
                line += "\n"
                f.write(line)

                for inst in self.instances:
                        line = str(inst.Id) + ", " + str(inst.clusterId) + ", " + str(inst.x) + ", " + str(inst.y)
                        for val in inst.attributeValues:
                                line += ", " + str(val)
                        if hasattr(inst, 'classRate'):
                                line += ", " + str(inst.classRate)
                                
                        line += "\n"
                        f.write(line)
                
        def exportDataSetToArff(self, f, fileName):
            f.write("@relation " + fileName + "\n\n")

        #write attributes
            for attr in self.attributes:
                    line = "@attribute " + attr.attributeName + " "
            if attr.isNumeric == True: line += "numeric"
            else:
                vals = ""            
                for val in attr.attributeValues:
                        if vals != "": vals += ","
                        vals += val
                line += "{" + vals + "}"
                line += "\n"
            f.write(line)

            f.write("\n@data\n")

            for inst in self.instances:
                        line = ""
                        for val in inst.attributeValues:
                                if line != "": line += ","
                                line += str(val)
                        line += "\n"
                        f.write(line)

    def distList(self):
        output=[]
        normed=self.NormalizeDataSet(False)
        for i in range(self.instances.__len__()):
            for j in range(i+1, self.instances.__len__()):
                output.append(normed.dist(normed.instances[i], normed.instances[j]))
        return output
        
    def findCr(self):
        dists=self.distList()
        L=[i for i in dists if i!=0]
        L.sort()
        n=len(self.instances)
        result=float(2)/(n*(n-1))
        L_last=L[0]
        Cr=[]
        r=[]
        for i in range(len(L)-1):
            if L[i+1]>L_last:
                Cr.append(i*result)
                r.append(L[i])
            L_last=L[i+1]
        return(Cr, r)
        
    def estimateID(self, percentile=1.0/16):
        Cr, r = self.findCr()
        n=int(len(r)*percentile)
        if n<5: n=5
        d1=(np.log(Cr[1:n])-np.log(Cr[1]))/(np.log(r[1:n])-np.log(r[1]))
        return np.median(d1), n   


def mergeDataSets(dataSets):
    if len(dataSets) == 0: return EmptyDataSet()
    dataSet = dataSets[0].copyDataSet()
    for ds in dataSets:
        for instance in ds.instances:
            newInst = instance.createInstance()
            newInst.attributeValues = []
            for val in instance.attributeValues:
                newInst.attributeValues.append(val)
            dataSet.addInstance(newInst)
    return dataSet
def EmptyDataSet():
        return DataSet()

class Pair:
    def __init__(self, x, c):
        self.x = x
        self.c = c

class Quadrant:
    SeqNr = 1
    def __init__(self, parent, childNr, projectedDataset, level, minX, minY, maxX, maxY):
        self.projectedDataSet = projectedDataset
        if (parent != None): self.Id = parent.Id + "." + str(childNr)
        else: self.Id = str(childNr)
        #definition
        self.level = level
        self.parent = parent
        self.density = None
        self.minX = minX
        self.minY = minY 
        self.maxX = maxX
        self.maxY = maxY
        
        self.medianX = None
        self.medianY = None
        self.child1 = None
        self.child2 = None
        self.child3 = None
        self.child4 = None
        self.neighbors = None
        self.isLeaf = False

        self.cluster = None
    
    def divide(self, maxSize):
        size = len(self.projectedDataSet.instances)
        self.projectedDataSet.computeClassStatistics()

        self.isLeaf = False

        if self.level > 10 or len(self.projectedDataSet.instances) < maxSize:
                self.isLeaf = True
        else:
            self.projectedDataSet.instances.sort(key = lambda instance: instance.x)
            self.medianX = self.projectedDataSet.instances[size/2].x

            if self.level == 0: 
                self.minX = self.projectedDataSet.instances[0].x
                self.maxX = self.projectedDataSet.instances[size - 1].x

            self.projectedDataSet.instances.sort(key = lambda instance: instance.y)
            self.medianY = self.projectedDataSet.instances[size/2].y

            if self.level == 0:
                self.minY = self.projectedDataSet.instances[0].y
                self.maxY = self.projectedDataSet.instances[size - 1].y

            ds1 = self.projectedDataSet.copyDataSet()
            ds2 = self.projectedDataSet.copyDataSet()
            ds3 = self.projectedDataSet.copyDataSet()
            ds4 = self.projectedDataSet.copyDataSet()

            for inst in self.projectedDataSet.instances:
                if (inst.x <= self.medianX and inst.y <= self.medianY): ds1.addInstance(inst)
                elif (inst.x > self.medianX and inst.y <= self.medianY): ds2.addInstance(inst)
                elif (inst.x <= self.medianX and inst.y > self.medianY): ds3.addInstance(inst)
                elif (inst.x > self.medianX and inst.y > self.medianY): ds4.addInstance(inst)
 
            if len(ds1.instances) == size or len(ds2.instances) == size or len(ds3.instances) == size or len(ds4.instances) == size:
                self.isLeaf = True
        
            if not self.isLeaf:
                self.child1 = Quadrant(self, "1", ds1, self.level + 1, self.minX, self.minY, self.medianX, self.medianY)
                self.child2 = Quadrant(self, "2", ds2, self.level + 1, self.medianX, self.minY, self.maxX, self.medianY)
                self.child3 = Quadrant(self, "3", ds3, self.level + 1, self.minX, self.medianY, self.medianX, self.maxY)
                self.child4 = Quadrant(self, "4", ds4, self.level + 1, self.medianX, self.medianY, self.maxX, self.maxY)
            
                self.child1.divide(maxSize)
                self.child2.divide(maxSize)
                self.child3.divide(maxSize)
                self.child4.divide(maxSize)

    def getAllLeaves(self, listOfLeaves, maxSurface = None):
        if self.parent == None:
            maxSurface = (self.maxX - self.minX) * (self.maxY - self.minY)
    
        if self.isLeaf:
            listOfLeaves.append(self)
            nrInstances = len(self.projectedDataSet.instances)
            surface = ((self.maxX - self.minX)*(self.maxY - self.minY))/maxSurface
            if surface == 0: self.density = 0
            else: self.density = nrInstances/surface

        if (self.child1 != None): self.child1.getAllLeaves(listOfLeaves, maxSurface)
        if (self.child2 != None): self.child2.getAllLeaves(listOfLeaves, maxSurface)
        if (self.child3 != None): self.child3.getAllLeaves(listOfLeaves, maxSurface)
        if (self.child4 != None): self.child4.getAllLeaves(listOfLeaves, maxSurface)

    def printLeaf(self):
        if not self.isLeaf:
            return

        line = ''
        
        #Id
        line += str(self.Id).ljust(15) + '\t'

        #Nr Instances
        line += str(len(self.projectedDataSet.instances)).rjust(4) + '\t'

        #Surface
        density = '%.2f' % self.density
        line += str(density).rjust(10) + '\t'
    

        #for neighbor in self.neighbors: line += neighbor.Id + " "    


        print line


    def printQuadrantToFile(self, clusterFileName):
        if self.level == 0:
            f = open(clusterFileName, 'w')
            f.close()


        if not self.isLeaf:
            f = open(clusterFileName, 'a')
            f.write(str(self.medianX) + " " + str(self.minY) + "\n")
            f.write(str(self.medianX) + " " + str(self.maxY) + "\n")
            f.write("\n")
            f.write(str(self.minX) + " " + str(self.medianY) + "\n")
            f.write(str(self.maxX) + " " + str(self.medianY) + "\n")
            f.write("\n")
            f.close()

        if self.child1 != None: self.child1.printQuadrantToFile(clusterFileName)
        if self.child2 != None: self.child2.printQuadrantToFile(clusterFileName)
        if self.child3 != None: self.child3.printQuadrantToFile(clusterFileName)
        if self.child4 != None: self.child4.printQuadrantToFile(clusterFileName)
        
    def printStatistics(self, classAttribute = None):
        if self.projectedDataSet.isClassNumeric == True:
            self.printStatistics_NumericClass(self.projectedDataSet.minScore, self.projectedDataSet.maxScore)
        elif self.projectedDataSet.isClassNumeric == False:
            self.printStatistics_DiscreteClass(classAttribute)

    def printStatistics_NumericClass(self, minScore, maxScore):
        line = ''
        for i in range(self.level): line += "| "
        line += "# " + str(len(self.projectedDataSet.instances))
        for i in range(20 - len(line)): line += " "

        strVariance = ""
        strV = "  "

        strVariance = ('%.2f' % (self.projectedDataSet.varianceScore**0.5)).rjust(7)

        if self.level == 0:
            strV = "  "
        else:
            if self.parent.projectedDataSet.varianceScore > self.projectedDataSet.varianceScore: strV = " L"
            else: strV = " H"


        if self.isLeaf:
            line += " <--  "
            line += boxPlot(minScore, 
                    maxScore, 
                    self.projectedDataSet.minScore, 
                    self.projectedDataSet.q1Score, 
                    self.projectedDataSet.medianScore, 
                    self.projectedDataSet.q3Score, 
                    self.projectedDataSet.maxScore)
            line += strVariance
            line += strV
            print line 
        else:
            line += "      "
            line += boxPlot(minScore, 
                    maxScore, 
                    self.projectedDataSet.minScore, 
                    self.projectedDataSet.q1Score, 
                    self.projectedDataSet.medianScore, 
                    self.projectedDataSet.q3Score, 
                    self.projectedDataSet.maxScore)
            line += strVariance
            line += strV
            print line
            if self.child1 != None: self.child1.printStatistics_NumericClass(minScore, maxScore)
            if self.child2 != None: self.child2.printStatistics_NumericClass(minScore, maxScore)
            if self.child3 != None: self.child3.printStatistics_NumericClass(minScore, maxScore)
            if self.child4 != None: self.child4.printStatistics_NumericClass(minScore, maxScore)

    def printStatistics_DiscreteClass(self, classAttribute):
        line = ''
        for i in range(self.level): line += "| "
        line += "# " + str(len(self.projectedDataSet.instances))
        for i in range(20 - len(line)): line += " "

        classFreqStr = ""
        strEntropy = ""
        strE = "  "

        for c in classAttribute.attributeValues:
            classFreqStr += c.rjust(2) + ": "
            p = 0
            if c in self.projectedDataSet.classFreq: 
                p = self.projectedDataSet.classFreq[c]
            classFreqStr += str(p).rjust(5) + ", "


        strEntropy = "  " + ('%.2f' % (self.projectedDataSet.entropy)).rjust(4)

        if self.level == 0:
                        strE = "  "
        else:
            if self.parent.projectedDataSet.entropy > self.projectedDataSet.entropy: strE = " L"
            else: strE = " H"

        if self.isLeaf:
            line += " <--  "
            line += classFreqStr
            line += strEntropy
            line += strE
            print line
        else:
            #line += "      "
            #line += classFreqStr
            #line += strEntropy
            #line += strE
            print line
            if self.child1 != None: self.child1.printStatistics_DiscreteClass(classAttribute)
            if self.child2 != None: self.child2.printStatistics_DiscreteClass(classAttribute)
            if self.child3 != None: self.child3.printStatistics_DiscreteClass(classAttribute)
            if self.child4 != None: self.child4.printStatistics_DiscreteClass(classAttribute)


    def isNeighbor(self, quad):

        if (self.minY == quad.maxY) or (self.maxY == quad.minY):
            if not (self.minX > quad.maxX or self.maxX < quad.minX):
                return True

        elif (self.minX == quad.maxX) or (self.maxX == quad.minX):
            if not (self.minY > quad.maxY or self.maxY < quad.minY):
                return True

        return False

    def computeAllNeighbors(self, listOfLeaves):
        self.neighbors = []

        for quad in listOfLeaves:
            if self.isNeighbor(quad) and self.Id != quad.Id:
                self.neighbors.append(quad)

        self.neighbors.sort(key = lambda leaf: leaf.density)


def CreateQuadrants(quadrant, nrSplit):
    size = len(quadrant.projectedDataSet.instances)
    quadrant.projectedDataSet.computeClassStatistics()

    quadrant.projectedDataSet.instances.sort(key = lambda instance: instance.x)
    quadrant.minX = quadrant.projectedDataSet.instances[0].x
    quadrant.maxX = quadrant.projectedDataSet.instances[size - 1].x

    quadrant.projectedDataSet.instances.sort(key = lambda instance: instance.y)
    quadrant.minY = quadrant.projectedDataSet.instances[0].y
    quadrant.maxY = quadrant.projectedDataSet.instances[size - 1].y

    maxSurface = (quadrant.maxX - quadrant.minX)*(quadrant.maxY - quadrant.minY)

    minX = min(quadrant.minX, quadrant.minY)
    minY = minX

    maxX = max(quadrant.maxX, quadrant.maxY)
    maxY = maxX

    stepSize = float(maxX - minX)/float(nrSplit)

    print stepSize

    quadrants = []

    k = 0
    for i in range(nrSplit):
        for j in range(nrSplit):
            quadrants.append(Quadrant(None, str(k), DataSet(quadrant.projectedDataSet.isClassNumeric), 1, 
                        minX + stepSize*i, minY + stepSize*j,  
                        minX + stepSize*(i+1), minY + stepSize*(j+1), 0, 0, 1, 1))
            k += 1


    for inst in quadrant.projectedDataSet.instances:
        i = int(inst.x/stepSize)
        j = int(inst.y/stepSize)
        if i == nrSplit: i = i - 1
        if j == nrSplit: j = j - 1
        quad = quadrants[i*nrSplit + j]
        
        #if inst.x < quad.minX: or inst.x > quad.maxX:
        #    print "Error on X - " + str(inst.x) + " " + str(quad.minX) + " " + str(quad.maxX)

        #if inst.y < quad.minY or inst.y > quad.maxY:
        #    print "Error on Y - " + str(inst.y) + " " + str(quad.minY) + " " + str(quad.maxY)

        quad.projectedDataSet.addInstance(inst)
    

    quadrants2 = []
    for i in range(nrSplit):
        for j in range(nrSplit):
            quad = quadrants[i*nrSplit + j]
            quad.isLeaf = True
            nrInstances = len(quad.projectedDataSet.instances)
            surface = ((quad.maxX - quad.minX)*(quad.maxY - quad.minY))/maxSurface
            if nrInstances != 0:
                quad.density = float(nrInstances)/float(surface)
                quad.projectedDataSet.computeClassStatistics()
                quadrants2.append(quad)

    return quadrants2

class Cluster:
    def __init__(self, clusterId = None):
        self.clusterId = clusterId
        self.quadrants = []
        self.nrInstances = None
        self.surface = None
        self.density = None
        self.mergedDataSet = None
    def mergeQuadrants(self):
        if len(self.quadrants) == 0:
                self.mergedDataSet == EmptyDataSet()
                return
        self.mergedDataSet = self.quadrants[0].projectedDataSet.copyDataSet()
        for quad in self.quadrants:
            self.mergedDataSet.instances += quad.projectedDataSet.instances
        self.mergedDataSet.setClusterId(self.clusterId)
    def computeStatistics(self, maxSurface):
        self.mergedDataSet.computeClassStatistics()

        self.nrInstances = float(len(self.mergedDataSet.instances))
        self.surface = 0

        for quad in self.quadrants:
                self.surface += ((quad.maxX - quad.minX)*(quad.maxY - quad.minY))/maxSurface    
    
        if self.nrInstances == 0: self.density = 0
        elif self.surface == 0: self.density = 0
        else:
            self.density = self.nrInstances/self.surface
    def computeCentroid(self):
                if (self.mergedDataSet.NrInstances() == 0):
                        return None
                return self.mergedDataSet.computeCentroid()
                

    def exportToCSV(self, f):
                if self.mergedDataSet.NrInstances() != 0:
                        self.mergedDataSet.exportToCSV(f)
    
    def printClusterToFile(self, clusterFileName, color=None):
        if color == None: color = "#EE82EE"

        f = open(clusterFileName, 'a')

        #if self.mergedDataSet.isClassNumeric == True: 
        #    f.write("#MedianScore: " + str(self.mergedDataSet.medianScore).rjust(7) + "\n")
        #else:
        #    f.write("#Entropy: " + str(self.mergedDataSet.entropy) + "\n")
        
        for quad in self.quadrants: 
            f.write("set object rect from " + str(quad.minX) + "," + str(quad.minY) + " to " 
                + str(quad.maxX2) + "," + str(quad.maxY2) + " fc rgb \"" + color +  "\"\n")

        f.write(" ")
        f.write(" ")
        f.close()

    def printClusterStatistics(self, classAttribute = None):
        #line = "Cluster: " + str(len(clusters)).rjust(4)
        line = "Nr. of Quadrants: " + str(len(self.quadrants)).rjust(4)

        strDens = '%.2f' % self.density
        line += ", Density: " + strDens.rjust(12)

        line += ", Nr. Instances: " + str(int(self.nrInstances)).rjust(5)

        if self.mergedDataSet.isClassNumeric:
            line += ", MedianScore: " + str(self.mergedDataSet.medianScore).rjust(7)
            line += ", SdScore: " +  ('%.2f' % (self.mergedDataSet.varianceScore**0.5)).rjust(7)
        else:
            line += ", Frequencies - "
            for c in classAttribute.attributeValues:
                p = 0
                if c in self.mergedDataSet.classFreq:
                    p = self.mergedDataSet.classFreq[c]
                line += c.rjust(2) + ": " + str(p).rjust(5) + ", "

            line += "Entropy: " + ('%.2f' % (self.mergedDataSet.entropy)).rjust(4)
                
        print line
def ClusterProjectedInstances(dataSet, clusters):
        for instance in dataSet.instances:
            for cluster in clusters:
                for quadrant in cluster.quadrants:
                    if instance.x >= quadrant.minX and instance.x < quadrant.maxX and instance.y >= quadrant.minY and instance.y < quadrant.maxY:
                        instance.clusterId = cluster.clusterId
                        instance.originalInst.clusterId = cluster.clusterId
                        break
            if instance.clusterId != None: break

def GetClusterById(clusters, clusterId):
        if clusterId < len(clusters):
                if clusters[clusterId].clusterId == clusterId: return clusters[clusterId]
        for cluster in clusters:
                if cluster.clusterId == clusterId:
                        return cluster
        return None
        
def GetClusterCentroids(clusters):
        if (len(clusters) == 0): return EmptyDataSet()
        dataSet = clusters[0].mergedDataSet.copyDataSet()
        for cluster in clusters:
                centroid = cluster.computeCentroid()
                if (centroid != None):
                        centroid.Id = cluster.clusterId
                        centroid.clusterId = cluster.clusterId
                        dataSet.addInstance(centroid)
        if dataSet.isClassNumeric == False: dataSet.expectedEntropy = ComputeExpectedEntropy(clusters)
        dataSet.computeClassStatistics()
        return dataSet

def ComputeExpectedEntropy(clusters):
        expectedEntropy = 0
        nrAllInstances = 0
        for cluster in clusters:
                nrAllInstances += float(cluster.mergedDataSet.NrInstances())
        for cluster in clusters:
                expectedEntropy += (float(cluster.mergedDataSet.NrInstances())/nrAllInstances)*cluster.mergedDataSet.entropy
        return expectedEntropy
                

""""
Demos and Tests
===============

Demos
-----

The library codes has code that lets us implement a set of *demos* that can show off particular features. The functions inclded in the demos
will be marked with `@demo`; for example:

    @demo
    def demoed() : print "I am a demo"

"""

def demo(f=None,demos=[]): 
  if f: demos.append(f); return f
  for d in demos: 
    print '\n--|',d.func_name,'|','-'*40,'\n',d.__doc__,'\n'
    d()

"""

Tests
-----

Also, the library also supports  test functions that return a list of pairs `[(got,want)]` and the test is passed in `got==want`.

    @test
    def tested(): 
      thing = 22
      return [(22,thing),  # multiple test results can be returned
              (False, type thing = float)]

"""

def test(f=None,tests=[]): 
  if f: tests.append(f); return f
  ok=no=0
  for t in tests: 
    print "#",t.func_name + ': ',t.__doc__
    for n,(want,got) in  enumerate(t()):
      if want == got:
        ok += 1; print "CORRECT:",t.func_name,'question', n+1
      else:
        no += 1; print "WRONG  :",t.func_name,'question',n+1
  if tests:
    print '\n# Final score = %s/%s = %s%% CORRECT' \
            % (ok,(ok+no),round(100*ok/(ok+no)))

""""

In Use
------

All those  demos and all the tests can be exercised as follows:

    python moo.py -i 'demos()'
    python moo.py -i 'tests()'


"""

@test
def tested1():
  "Test functions return lists of (want,got) pairs"
  return [(1,1),
          (True,type(1) == int),
          (False,type(1) == float)]

@test
def tested2():
  "Test that the test code can catch a failure."
  return [(0,1)]


"""

Note that one test suite item will fail 
(just to test that the test suite can catch failing code) so the number of
correct tests is never  100%.

Math Stuff
==========

""" 

import math

def more(x,y): return x > y
def less(x,y): return x < y

def normd(d):
  sum,out = 0,{}
  for k in d : sum += d[k]
  for k in d : out[k] = round(100*d[k]/sum)
  return out

"""

Random Stuff
------------

"""

import random
any = random.uniform
normal= random.gauss
seed  = random.seed
shuffle = random.shuffle

def sometimes(p) : 
  "Returns True at probability 'p;"
  return p > any(0,1)

def one(lst): 
  "Returns one item in a list, selected at random"
  return lst[  int(any(0,len(lst) - 1)) ]

def randomPop(lst):
    return lst.pop(int(any(0,len(lst) - 1)))

def some(lst,p)  : 
  "Returns 'p'% of a list,selected at random."
  return [x for x in lst if sometimes(p)]

"""

String Stuff
===========

"""

import re,string,sys

sub=re.sub
ljust=string.ljust

def say(x) : sys.stdout.write(x); sys.stdout.flush()
"""

File Stuff
==========

"""

def lines(file, n=0, bad=r'["\' \t\r\n]',sep=',',shuffle=False) :
  if shuffle:
    all = [line for line in open(file,'r')]
    head = all[0]
    data = all[1:]
    random.shuffle(data)
    for line in [head] + data:
      n += 1
      yield sub(bad,"",line).split(sep),n 
  else: 
    for line in open(file,'r') :
      n += 1
      yield sub(bad,"",line).split(sep),n 

def readCK_CSV(filename):
    dataSet = DataSet()
    attlist=["@attribute setname string", "@attribute version string", "@attribute name string", "@attribute wmc numeric", "@attribute dit numeric", "@attribute noc numeric", "@attribute cbo numeric", "@attribute rfc numeric", "@attribute lcom numeric", "@attribute ca numeric", "@attribute ce numeric", "@attribute npm numeric", "@attribute lcom3 numeric", "@attribute loc numeric", "@attribute dam numeric", "@attribute moa numeric", "@attribute mfa numeric", "@attribute cam numeric", "@attribute ic numeric", "@attribute cbm numeric", "@attribute amc numeric", "@attribute max_cc numeric", "@attribute avg_cc numeric", "@attribute bug {0,1}"]
    dataSet.attributes=[processArffAttribute(att,ind) for ind, att in enumerate(attlist)]
    for ind, line in enumerate(open(filename,'r')):
        line = line.strip()
        if line.startswith('name'):
            continue
        dataSet.addInstance(processArffInstance(line, ind-1))
    return dataSet
        

def readArff(file, baseDataSet=None, bad=r'["\t\r\n]',sep=',') :
    dFlag = 0
    attrId = 0
    attrIndex = 0
    instId = 0
    countyAttributeIndex = -1
    latAttributeIndex = -1
    longitAttributeIndex = -1
    nemsAttrIndex = -1
    dataSet = DataSet()
    for line in open(file,'r') :
        line = line.strip()
        if not line.startswith('#') and line != '':
            if line.lower().startswith('@attribute'):
                attr = processArffAttribute(line,attrId)
                if attr.attributeName.lower().strip() == 'county':
                    countyAttributeIndex = attrIndex
                elif attr.attributeName.lower().strip() == 'latitude_$':
                    latAttributeIndex = attrIndex
                elif attr.attributeName.lower().strip() == 'longitude_$':
                    longitAttributeIndex = attrIndex
                elif attr.attributeName.lower().strip() == 'store_id':
                    nemsAttrIndex = attrIndex
                else:
                    dataSet.attributes.append(attr)
                    attrId += 1
                attrIndex += 1
            if dFlag == 1:
                dataSet.addInstance(processArffInstance(line,instId, countyAttributeIndex, latAttributeIndex, longitAttributeIndex, nemsAttrIndex))
                dataSet.isClassNumeric = dataSet.attributes[attrId-1].isNumeric
                classVal = dataSet.instances[instId].attributeValues[attrId-1]
                if dataSet.isClassNumeric == True: dataSet.instances[instId].classVal = float(classVal)
                else: dataSet.instances[instId].classVal = classVal
                instId += 1
            if line.lower() == '@data':
                dFlag = 1
    return dataSet

def processArffAttribute(line, i):
    attribute = Attribute()

    line = sub('@attribute', '', line).strip()

    attribute.Id = i

    ind = line.find(" ")
    if ind >= 0:
        attribute.attributeName = line[0:ind]
        line = line[ind:].strip()

    line = sub('{', '', line)
    line = sub('}', '', line)

    if line.lower() == 'numeric':
        attribute.isNumeric = True
    else:
        attribute.isNumeric = False

        attributeValues = line.split(',')
        for val in attributeValues:
            attribute.attributeValues.append(val.strip())
    
    return attribute

def processArffInstance(line, Id, countyAttrId=-1, latAttrId=-1, longitAttrId=-1, nemsAttrId=-1):
    instance = Instance()
    instance.Id = Id
    attributeVals = line.split(',')
    i = 0    
    for val in attributeVals:
        if i == countyAttrId: instance.county = val
        elif i == latAttrId: instance.lat = val
        elif i == longitAttrId: instance.longit = val
        elif i == nemsAttrId: instance.nemsId = val
        else: instance.attributeValues.append(val.strip())
        i += 1
    return instance

def printAllAttributes(dataSet):
    line = ''
    for attrId in dataSet.attributes:
        line = ''
        attribute = dataSet.attributes[attrId]
        #if attribute.isNumeric:
        #    print attribute.attributeName + str(attribute.minVal) + "," + str(attribute.maxVal)
        #line = attribute.attributeName + "," + str(attribute.isNumeric) + "," 
        #for r in attribute.attributeValues:
        #    line = line + r + " "
        #print line

def printAllInstances(dataSet):
    line = ''
    for i in range(dataSet.NrInstances()):
        instance = dataSet.instances[i]
        line = ''
        line = line + str(i) + ','
        line = line + instance.county + ','
        line = line + instance.attributeValues[dataSet.NrAttributes() - 1]
        print line

def printAllInstances2(dataSet, baseDataSet):
    for i in range(dataSet.NrInstances()):
        instance = dataSet.instances[i]
        baseInstance = baseDataSet.instances[i]        

        county = instance.county
        baseCounty = baseInstance.county

        class1 = instance.attributeValues[dataSet.NrAttributes() - 1]
        baseClass = baseInstance.attributeValues[baseDataSet.NrAttributes() - 1]

        if county != baseCounty or class1 != baseClass:
            print "Error"
        else:
            line = ''
            line = line + str(i) + ','
            line = line + county + ','
            line = line + class1
            print line

def getLabelFrequenciesFromPairs(pairs):
    classFreq = {}
    for pair in pairs:
        if pair.c not in classFreq: classFreq[pair.c] = 0
        classFreq[pair.c] += 1
    return classFreq

def estimateEntropy(classFreq):
    entropy = 0
    size = 0
    for c in classFreq: size += classFreq[c]

    if size == 0: return entropy 

    for c in classFreq:
        p = float(classFreq[c])/float(size)
        if p != 0:
            entropy += (-1)*p*math.log(p,2)
    return entropy

def computeClassMode(classFreq):
    maxFreq = 0
    maxFreqVal = None
    for val in classFreq:
        if classFreq[val] > maxFreq:
            maxFreq = classFreq[val]
            maxFreqVal = val
    return maxFreqVal


def combineClassFrequecies(classFreq1, classFreq2):
    classFreq = {}
    
    for c in classFreq1:
        classFreq[c] = classFreq1[c]

    for c in classFreq2:
        if c in classFreq: 
            classFreq[c] += classFreq2[c]
        else:
            classFreq[c] = classFreq2[c]

    return classFreq

def furthest_numeric(v, minV = 0, maxV = 1):
    if v < (float(maxV)-float(minV))/2:
        return maxV
    return minV        
    
def getAttributeValuesFromSplits(splits):
    values = []

    if len(splits) == 0:
        values.append("(-inf:+inf)")
        return values

    values.append("(-inf:" + str(splits[0]) + ")")
    for i in range(len(splits)-1):
        values.append("[" + str(splits[i]) + ":" + str(splits[i+1]) + ")")
    values.append("[" + str(splits[len(splits)-1]) + ":+inf)")
    return values

def getAttributeValuesFromSplits2(splits):
    values = []

    if len(splits) == 0:
        values.append("1")
        return values

    val = 1
    values.append(str(val))
    val += 1
    for i in range(len(splits)-1):
        values.append(str(val))
        val += 1
    values.append(str(val))
    val += 1
    return values

def discretizeValue(val, splits):
    if len(splits) == 0:
        return "(-inf:+inf)"
        
    i = 0
    cont = True
    while cont == True:
        if i == len(splits):
            cont = False
        elif val <= splits[i]:
            cont = False
        else:
            i += 1

    if i == len(splits):
        return "[" + str(splits[len(splits)-1]) + ":+inf)"

    if val == splits[i]:
        if i == len(splits)-1:
            return "[" + str(splits[i]) + ":+inf)"                          
        else:
            return "[" + str(splits[i]) + ":" + str(splits[i+1]) + ")"

    if val < splits[i]:
        if i == 0:
            return "(-inf:" + str(splits[i]) + ")"
        else:
            return "[" + str(splits[i-1]) + ":" + str(splits[i]) + ")"

    raise Exception("discritizeValue - val: " + str(val))    

def discretizeValue2(val, splits):
    if len(splits) == 0:
        return "1"
        
    i = 0
    cont = True
    while cont == True:
        if i == len(splits):
            cont = False
        elif val <= splits[i]:
            cont = False
        else:
            i += 1

    return str(i)


    if i == len(splits):
        return "[" + str(splits[len(splits)-1]) + ":+inf)"

    if val == splits[i]:
        if i == len(splits)-1:
            return "[" + str(splits[i]) + ":+inf)"                          
        else:
            return "[" + str(splits[i]) + ":" + str(splits[i+1]) + ")"

    if val < splits[i]:
        if i == 0:
            return "(-inf:" + str(splits[i]) + ")"
        else:
            return "[" + str(splits[i-1]) + ":" + str(splits[i]) + ")"

    raise Exception("discritizeValue - val: " + str(val))    


def discretizeClassToBinary(readFileName, writeFileName):
    writeFile = open(writeFileName, 'w')

    dFlag = 0
    for line in open(readFileName,'r') :
        line = line.strip()
        if not line.startswith('#') and line != '':

            if dFlag == 1:
                ind = line.rfind(",")
                classVal = int(line[ind + 1:])
                if classVal > 0: line = line[:ind+1] + "1"            

            if line.lower() == '@data':
                dFlag = 1

        writeFile.write(line + "\n")

    writeFile.close()


def discretizeClassToBinary_2(readFileName, writeFileName):
    writeFile = open(writeFileName, 'w')

    firstLine = True
    nrAttributes = 0
    skipAttributes = []
    bugColumn = -1

    for line in open(readFileName,'r') :
        line = line.strip()        
        if line == "": continue        
        if firstLine == True:
            firstLine = False
            writeFile.write("@relation " + readFileName + "\n")
            writeFile.write("\n")
            attributes = line.split(",")
            i = 0            
            for attr in attributes:
                if attr.lower() == "name" or attr.lower() == "version":
                    skipAttributes.append(i)
                elif attr.lower() == "bug":
                    writeFile.write("@attribute bug {0,1}\n")
                    bugColumn = i
                else:
                    writeFile.write("@attribute " + attr + " numeric\n")
                i += 1
            nrAttributes = i
            writeFile.write("\n")
            writeFile.write("@data\n")
        else:
            vals = line.split(",")
            newLine = ""            
            for i in range(nrAttributes):
                if i == bugColumn:
                    classVal = int(vals[i])
                    if classVal == 0:
                        newLine += "0"
                    else:
                        newLine += "1"
                elif i not in skipAttributes:
                    newLine += vals[i] + ","
            writeFile.write(newLine + "\n")

    writeFile.write("\n")
    writeFile.close()

def mergeNemsFiles(idsFileName, surveyFileName, writeFileName):
    writeFile = open(writeFileName, 'w')

    firstLine = True
    
    #load instances
    instances = []
    for line in open(idsFileName,'r'):
        line = line.strip()        
        if line == "": continue        
        if firstLine == True:
            firstLine = False
        else:
            vals = line.split(",")
            instance = Instance()
            instance.nemsId = vals[0].strip()
            instance.county = vals[1].strip()
            instance.outletId = vals[2].strip()
            instance.classVal = vals[3].strip()
            instance.latitude = vals[4].strip()
            instance.longitude = vals[5].strip() 
            instances.append(instance)

    firstLine = True
    i = 0
    for line in open(surveyFileName,'r'):
        line = line.strip()
        if line == "": continue        
        if firstLine == True:
            firstLine = False
            writeFile.write(line + ",latitude,longitude\n")
        else:
            vals = line.split(",")
            inst = findInstanceByNemsId(instances, vals[0].strip())
            if inst == None: print "Error: - Store with Id: " + vals[0].strip() + " not found in IDs file!"
            writeFile.write(line + "," + inst.latitude + "," + inst.longitude + "\n")
            i += 1
            #if inst.county != vals[1].strip(): print "Error: - StoreId: " + vals[0].strip() + " - County does not match!"
             #if inst.outletId != vals[2].strip(): print "Error: - StoreId: " + vals[0].strip() + " - Outlet does not match!" + inst.outletId + ", " + vals[2]
            #if inst.classVal != vals[3].strip(): print "Error: - StoreId: " + vals[0].strip() + " - Score does not match!"
            #print inst.classVal
            #print vals[3]
            #return

    writeFile.close()

def findInstanceByNemsId(instances, nemsId):
    for inst in instances:
        if inst.nemsId == nemsId:
            return inst
    return None

"""

Histogram Stuff
================

"""
def boxPlotHeader(minV, maxV):
    line = ''
    for i in range(20): line += " "
    line += '%.2f' % minV
    print line 


def boxPlot(minV, maxV, min1,  q1, median, q3, max1):
    line = ''

    if min1 != None and q1 != None and median != None and q3 != None and max1 != None:

        indMin = int(50 * (min1 - minV)/(maxV - minV))
        for i in range(indMin): line += ' '

        line += '['
    
        indQ1 = int(50*(q1 - minV)/(maxV - minV))
    
        for i in range(indQ1-indMin): line += ' '

        indMedian = int(50 * (median - minV)/(maxV - minV))


        for i in range(indMedian - indQ1 - 1): line += "-"
        line += "|"

        indQ3 = int(50 * (q3 - minV)/(maxV - minV))
    
        for i in range(indQ3 - indMedian): line += "-"

        indMax = int(50 * (max1 - minV)/(maxV - minV))
        if (indMax > 50): indMax = 50

        for i in range(indMax-indQ3-1): line += ' '

        line += "]"


    for i in range(52 - len(line)): line += " "


    return line
    
        
def histogram(lst, decimals=2):
  d = {}
  r = 10**decimals
  for x in lst:
    x= int(x) if decimals==0 else math.ceil(x * r) / r
    d[x] = d.get(x,0) + 1
  return d

def printh(h,shrink=1,header=None,pre="") :
  if header: print header 
  for key in h: 
    print pre+ (str(key).rjust(5)), \
        str(h[key]).rjust(5),\
        '*' * (h[key]/shrink)


def split(line):
    tokens = []
    currentToken = ""
    for c in line:
        if c == ' ':
            if currentToken != "": tokens.append(currentToken)
            currentToken = ""
        else:
            currentToken += c
    return tokens



def insertItem(lst, ind, item):
    if ind > len(lst):
        print "Error - incorrect value of ind"
        return    

    #this function insert item at the position ind and shifs the other items right
    lst.append(None)

    i = len(lst) - 1
    while i > ind: 
        lst[i] = lst[i-1]
        i = i - 1

    lst[ind] = item

def getInsertIndex(lst, item, level = None,  minInd = None, maxInd = None):
    #print str(minInd) + ", " + str(maxInd)
    if level == None: level = 0
    else: level += 1

    if len(lst) == 0: return 0

    #if level == 5: return

    if minInd == None: minInd = 0
    if maxInd == None: maxInd = len(lst) - 1

    if minInd >= maxInd:
        if item < lst[minInd]: return minInd
        else: return minInd + 1

    medIndex = minInd + (maxInd - minInd)/2

    #print str(level) + ", " +  str(minInd) + ", " + str(maxInd) + ", " + str(medIndex)

    if item < lst[medIndex]:
        return getInsertIndex(lst, item, level, minInd, medIndex - 1)
    else: 
        return getInsertIndex(lst, item, level,  medIndex+1, maxInd)


def getInsertIndex_2(lst, item):
    if (len(lst) == 0): return 0

    ind = len(lst) - 1
    while ind >= 0:
        if lst[ind] <= item: return (ind + 1)
        ind -= 1

    return 0

def removeQuadrantFromList(listOfQuadrants, quadrant):
    for quad in listOfQuadrants:
        if quadrant.Id == quad.Id:
            listOfQuadrants.remove(quad)
            return
def unique(l):
    uniqueList = []
    for x in l:
        if x not in uniqueList:
            uniqueList.append(x)
    return uniqueList

def airDistance(lat1, lon1, lat2, lon2):
    lat1 = float(lat1)
    lon1 = float(lon1)
    lat2 = float(lat2)
    lon2 = float(lon2)
    radius = 6371 # km
    
    dlat = math.radians(lat2-lat1)
    dlon = math.radians(lon2-lon1)

    a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) * math.sin(dlon/2) * math.sin(dlon/2)

    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))

    d = radius * c
 
    return d

def findMinAirDistance(inst, listOfInstances):
    minDist = 100000000000
    for inst2 in listOfInstances:
        dist = airDistance(inst.lat, inst.longit, inst2.lat, inst2.longit)
        if dist < minDist:
            minDist = dist
    return minDist

@demo
def histogramed():
   "What histogram is seen in 1000 samples of a normal(10,2) curve?"
   printh(histogram([round(normal(10,2)) for x in range(1000)]),
          shrink=10)
     
